#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define mid (l+r>>1LL)
#define repn(x) rep(x,1,n)
#define repm(x) rep(x,1,m)
#define pb push_back
#define Pi pair<int,int>
#define e(x) for(int i=h[x],y=to[i];i;i=nxt[i],y=to[i])
#define E(x) for(auto y:p[x])
namespace IO
{ 
	char Is[(1<<21)+10],Os[(1<<21)+10];
	int Ipt,Opt;
	char gc()
	{
		if(Ipt==1<<21)Ipt=0;
		if(!Ipt){Is[fread(Is,1,1<<21,stdin)]=0;}
		return Is[Ipt++];
	}
	void flush(){fwrite(Os,1,Opt,stdout);Opt=0;}
	void pc(char x)
	{
		if(Opt==1<<21)flush();
		Os[Opt++]=x;
	}
	int read()
	{
		int x=0;char ch=gc();while(ch<'0'||ch>'9')ch=gc();while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=gc();return x;
	}
}
using namespace IO;
#define LL __int128
inline void pf(LL x){if(x>=10)pf(x/10);putchar((x%10)+'0');}
const int N=2e6+5,M=1e6+5,inf=(1LL<<31)-1,mod=1e9+7;
const ll llf=1e18;
inline void add(int &a,int b){((a+=b)>=mod) and (a-=mod);}
inline int Add(int a,int b){return add(a,b),a;}
inline int mul(int a,int b){return 1LL*a*b%mod;}
inline void Mul(int &a,int b){a=mul(a,b);}
inline void red(int &a,int b){add(a,mod-b);}
inline int Red(int a,int b){return red(a,b),a;}
inline int qp(int a,int b){if(!b)return 1;int c=qp(a,b>>1);Mul(c,c);if(b&1)Mul(c,a);return c;}
int testid,n,m,a[N],b[N];
// dp[i][j] 表示前 i 个，最后一个是 j 的最大值
ll f[5005],F[5005],Val[N];
inline void subtask1(){
	int A=0;
	rep(i,1,n-1)A=max(A,a[i]);
	rep(i,0,n+1)Val[i]=0;
	repm(i)Val[i]+=b[i],Val[i+n-m+1]-=b[i];
	repn(i)Val[i]+=Val[i-1];
	rep(i,0,A)f[i]=Val[1]*i;
	rep(i,2,n){
		F[0]=f[a[i-1]];
		rep(j,1,a[i-1])F[j]=max(F[j-1],Val[i]*j+f[a[i-1]-j]);
		rep(j,a[i-1]+1,A)F[j]=F[j-1];
		rep(j,0,A)f[j]=F[j];
	}
	cout <<f[A]<<'\n';
}
// 当前无论如何都尽量往大了选，不仅对当前有利，还能使后面选择空间变大
mt19937 rd(time(0));
inline void subtask2(){
	ll Sum=a[1],Nw=a[1];
	rep(i,2,n){
		ll W=a[i-1]-Nw;
		if(i!=n)W=min(W,(ll)a[i]);
		Sum+=W,Nw=W;
	}
	LL ans=Sum;
	ans*=b[1];
	pf(ans),putchar('\n');
}
bool vis[N];
inline void subtaskrand(){
	rep(i,0,n+1)Val[i]=0;
	repm(i)Val[i]+=b[i],Val[i+n-m+1]-=b[i];
	repn(i)Val[i]+=Val[i-1];
	LL ans=0;
	int l=1,r=n;
	int ps=l;
	while((double)clock()/CLOCKS_PER_SEC<=0.94){
		int p=ps+rd()%(r-ps+1);
		while(vis[p])p--;
		vis[p]=1;
		while(ps<=r&&vis[ps])ps++;
		LL Sum=0,Nw=0;
		Sum=Nw*b[p];
		rep(i,p+1,n){
			ll W=a[i-1]-Nw;
			if(i!=n)W=min(W,(ll)a[i]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		Nw=0;
		per(i,p-1,1){
			ll W=a[i]-Nw;
			if(i!=1)W=min(W,(ll)a[i-1]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		ans=max(ans,Sum);
		if(ps==r+1)break;
	}
	pf(ans),putchar('\n');
}
inline void subtask3(){
	rep(i,0,n+1)Val[i]=0;
	repm(i)Val[i]+=b[i],Val[i+n-m+1]-=b[i];
	repn(i)Val[i]+=Val[i-1];
	LL ans=0;
	repn(p){
		LL Sum=0,Nw;
		Nw=0;
		Sum=Nw*b[p];
		rep(i,p+1,n){
			ll W=a[i-1]-Nw;
			if(i!=n)W=min(W,(ll)a[i]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		Nw=0;
		per(i,p-1,1){
			ll W=a[i]-Nw;
			if(i!=1)W=min(W,(ll)a[i-1]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		ans=max(ans,Sum);
	}
	pf(ans),putchar('\n');
}
inline void subtaskall(){
	rep(i,0,n+1)Val[i]=0;
	repm(i)Val[i]+=b[i],Val[i+n-m+1]-=b[i];
	repn(i)Val[i]+=Val[i-1];
	LL ans=0;
    int G=m;
	rep(p,max(1,G-10),min(n,G+10)){
		LL Sum=0,Nw;
		Nw=0;
		Sum=Nw*b[p];
		rep(i,p+1,n){
			ll W=a[i-1]-Nw;
			if(i!=n)W=min(W,(ll)a[i]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		Nw=0;
		per(i,p-1,1){
			ll W=a[i]-Nw;
			if(i!=1)W=min(W,(ll)a[i-1]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
        if(Sum>=ans)ans=Sum;
		ans=max(ans,Sum);
	}
    G=n-m+1;
    rep(p,max(1,G-10),min(n,G+10)){
		LL Sum=0,Nw;
		Nw=0;
		Sum=Nw*b[p];
		rep(i,p+1,n){
			ll W=a[i-1]-Nw;
			if(i!=n)W=min(W,(ll)a[i]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
		Nw=0;
		per(i,p-1,1){
			ll W=a[i]-Nw;
			if(i!=1)W=min(W,(ll)a[i-1]);
			Sum+=(LL)W*Val[i],Nw=W;
		}
        if(Sum>=ans)ans=Sum;
		ans=max(ans,Sum);
	}
	pf(ans),putchar('\n');
}
inline void Main(){
	n=read(),m=read();
	rep(i,1,n-1)a[i]=read();
	repm(i)b[i]=read();
	if(testid<=6)return subtask1();
	if(testid<=8)return subtaskrand();
	if(testid>=12&&testid<=15)return subtask3();
	return subtaskall();
}
signed main(){
	freopen("festival.in","r",stdin);
	freopen("festival.out","w",stdout);
	testid=read();
	int T=read();
	while(T--)Main();
	return 0;
}